import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    //创建二叉树节点类
    public static class treeNote{
        char name;//节点序号名
        int val;//数值域
        treeNote left;//左节点
        treeNote right;//右节点
        //提供节点带参数的构造方法
        public treeNote(char name, int val) {
            this.name = name;
            this.val = val;
        }
        //重写toString方法

        @Override
        public String toString() {
            return "treeNote{" +
                    "节点序号=" + name +
                    ", val=" + val +
                    '}';
        }
    }

    //二叉树根节点
    treeNote root;

    //手动创建一颗二叉树，并以root为根节点
    public void createBinaryTree(){
        treeNote A=new treeNote('A',1);
        /*treeNote B=new treeNote('B',2);
        treeNote C=new treeNote('C',3);
        treeNote D=new treeNote('D',4);
        treeNote E=new treeNote('E',5);
        treeNote F=new treeNote('F',6);
        treeNote G=new treeNote('G',7);

        A.left=B;
        A.right=C;
        B.right =E;
        B.left=D;
        C.right=G;
        C.left=F;*/
        root=A;
    }

    // 前序遍历(根左右)
    //思路：先打印每个根结点，再打印根节点的左节点，在打印右节点
    public void preOrder(treeNote root){
        if(root==null){
            return;
        }
        System.out.println(root);
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历(左根右)
    //思路：先打印每个根节点的左结点，再打印根节点，在打印根节点的右节点
    void inOrder(treeNote root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.println(root);
        inOrder(root.right);

    }
    // 后序遍历(左右根)
    //思路：先打印每个根结点的左节点，再打印根节点的右节点，在打印根节点
    void postOrde(treeNote root){
        if(root==null){
            return;
        }
        postOrde(root.left);
        postOrde(root.right);
        System.out.println(root);
    }

    // 层序遍历
    //思路1：利用队列实现
    void sequenceOrdeQuene(treeNote root){
        if(root==null){return;}
        Queue<treeNote> queue=new LinkedList<>();//创建队列对树的每一层节点进行储存
        queue.offer(root);
        while(!queue.isEmpty()){
            System.out.println(queue.peek());
            if(queue.peek().left!=null){
                queue.offer(queue.peek().left);
            }
            if(queue.peek().right!=null){
                queue.offer(queue.peek().right);
            }
            queue.poll();
        }
    }

    // 层序遍历
    //思路2：利用顺序表实现(顺序表构造二维数组)，将每层节点数据作为一个数组，然后将每层数组合并
    //将二叉树的每一层节点数据都储存在一个临时顺序表中，并利用队列将当前节点的下一层节点数据入队
    List<List<Character>> sequenceOrderArrayList(treeNote root){
        List<List<Character>> List=new ArrayList<>();
        if(root==null){return null;}
        Queue<treeNote> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            List<Character> sequenseList=new ArrayList<>();
            while(size!=0){
                sequenseList.add(queue.peek().name);
                if(queue.peek().left!=null){
                    queue.add(queue.peek().left);
                }
                if(queue.peek().right!=null){
                    queue.add(queue.peek().right);
                }
                queue.poll();
                size--;
            }
            List.add(sequenseList);
        }
           return List;
    }

    // 获取树中节点的个数(遍历法)
    public static int count;
    int sizeTraverse(treeNote root){
        if(root==null){return 0;}
        count++;
        sizeTraverse(root.left);
        sizeTraverse(root.right);
        return count;
    }
    // 获取树中节点的个数(子问题思路方法)
    int sizeSub(treeNote root){
        if(root==null){return 0;}
        return sizeSub(root.left)+sizeSub(root.right)+1;
    }

    // 获取叶子节点的个数(遍历法)
    public static int leafCount;
    int getLeafNoteTraverse(treeNote root){
        if(root==null){return 0;}
        if(root.left==null&&root.right==null){
            leafCount++;
        }
        return leafCount;
    }

    // 获取叶子节点的个数(子问题思路方法)
    int getLeafNoteSub(treeNote root){
        if(root==null){return 0;}
        if(root.right==null&&root.left==null){
            return 1;
        }
        return getLeafNoteSub(root.left)+getLeafNoteSub(root.right);

    }

    // 获取第K层节点的个数
    int getKLevelTreeNote(treeNote root,int k){
        if(root==null){return 0;}
        if(k==1){return 1;}
        return getKLevelTreeNote(root.left,k-1)+getKLevelTreeNote(root.right,k-1);
    }
    //获取二叉树的高度
    int getTreeHeight(treeNote root){
        if(root==null){return 0;}
        int left=getTreeHeight(root.left);
        int right=getTreeHeight(root.right);
        return left>right?left+1:right+1;
    }
    // 检测值为value的元素是否存在
    treeNote find(treeNote root, int val){
        if(root==null){return null;}
        if(root.val==val){
            return root;
        }
        treeNote leftTreeNote=find(root.left,val);
        if(leftTreeNote!=null){
            return leftTreeNote;
        }
        treeNote rightTreeNote= find(root.right,val);
        if(rightTreeNote!=null){
            return rightTreeNote;
        }
        return null;
    }

    // 判断一棵树是不是完全二叉树
    //方法：与层序遍历的方法相似(利用队列)
    boolean isCompleteTree(treeNote root){
        if(root==null) return true;
        Queue<treeNote> queue=new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            treeNote cur=queue.peek();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            queue.poll();
            if(queue.peek()==null){
                break;
            }
        }

        while(!queue.isEmpty()){
            treeNote cur=queue.peek();
            if(cur!=null){
                return false;
            }else{
                queue.poll();
            }
        }
        return true;
    }

    //检查两颗树是否相同
    //思路：先判断根节点，在判断左树，然后右树（递归）
    boolean isSameTree(treeNote root1,treeNote root2){
        //排除这两棵树中存在空树的情况
        if(root1==null&&root1!=null) return false;
        if(root1!=null&&root2==null) return false;
        if(root1==null&&root2==null) return true;

        if(root1.val==root2.val&&isSameTree(root1.left,root2.left)&&isSameTree(root1.right,root2.right)){
            return true;
        }else{
            return false;
        }

    }

    //判断一棵树是否为另一颗树的子树
    boolean isSubtree(treeNote root, treeNote subRoot){
        //排除这两棵树中存在空树的情况
        if(root==null&&subRoot!=null) return false;
        if(root!=null&&subRoot==null) return false;
        if(root==null&&subRoot==null)
        if (isSameTree(root,subRoot)) {
            return true;
        }
        return isSubtree(root.left,subRoot)||isSameTree(root.right,subRoot);
    }

    //判断一颗二叉树是否是平衡二叉树
    boolean isBalanced(treeNote root){
        if(root==null) return true;
        int left=getTreeHeight(root.left);
        int right=getTreeHeight(root.right);
        //boolean flag=getTreeHeight(root)<=1;
        if(Math.abs(left-right)>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);

    }

    //打印二叉树的镜像二叉树
    public void mirrorTree(treeNote root) {
        if(root==null) return ;
        Queue<treeNote> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            treeNote cur=queue.peek();
            treeNote left=null;
            treeNote right=null;
            //treeNote index=null;
            if(cur!=null){
                left=cur.left;
                right=cur.right;
                queue.offer(right);
                queue.offer(left);
            }
            System.out.println(queue.peek()+" ");
            queue.poll();
        }

    }



    public static boolean flag=false;
    public int getTreeHeight9(treeNote root){
        if(root==null){return 0;}
        int left=getTreeHeight9(root.left);
        int right=getTreeHeight9(root.right);
        if(Math.abs(left-right)>1){
            flag=true;
        }
        return left>right?left+1:right+1;
    }
    public boolean isBalanced9(treeNote root){
        if(root==null) return true;
        int a=getTreeHeight9(root);
        if(flag==true){return false;}
        return true;

    }

}
